import connectTree.Node;

public class Solution117 {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node head = root;
        Node pre = null, cur;
        while (head != null && head.left == null && head.right == null) {
            head = head.next;
        }
        if (head != null) {
            pre = head.left == null ? head.right : head.left;
        }
        Node nextLevel = pre;
        while (head != null) {
            cur = head.right;
            if (cur == pre || cur == null) {
                head = head.next;
                while (head != null && head.left == null && head.right == null) {
                    head = head.next;
                }
                if (head != null) {
                    cur = head.left == null ? head.right : head.left;
                }
            }
            if (head != null) {
                pre.next = cur;
                pre = cur;
            }
        }
        connect(nextLevel);
        return root;
    }

}
